1. Field of the Invention
This invention relates to a method and apparatus for allocating CRC (Cyclic Redundancy Check) codes in a flash ROM (Read-Only Memory), and more specifically a method and apparatus that can effectively reduce the times of erasing CRC codes.
2. Description of Related Art
It is very important for organizations and private users alike that electronic data be written to and read from a storage system quickly and reliably. A storage system may be logically divided into a plurality of data blocks, with each data block being further divided into a plurality of bytes. One method widely used to ensure reliable reading and writing of data is to perform a CRC (Cyclic Redundancy Check) on the data. When the data is written to the storage system, CRC codes are generated and saved in one or more bytes that are predefined in position. And when the data is read from the storage system, its CRC codes are read as well and compared to the newly calculated CRC codes associated with data read. If the newly calculated CRC codes match the stored CRC codes, the data is likely to be correct. Should the newly calculated CRC codes not match the stored CRC codes, there is something wrong with data read.
A conventional storage system may use semiconductors, magnetic devices or optical devices as its storage medium. A typical storage system generally comprises erasable read only memory, such as flash ROM and EEPROM (Electrically Erasable Programmable Read Only Memory). Flash ROM and EEPROM can both retain data while power is off, and can update the data according to new input data. There are some differences between flash ROM and EEPROM. EEPROM needs a voltage higher than normal to erase the data, so an additional device is always needed to accomplish erasing of data. Flash ROM can work under a normal voltage while erasing the data. In addition, only one byte at a time can be erased in an EEPROM, while a plurality of bytes at a time can be erased in a flash ROM. However, flash ROM has problems such as a limited number of erasures, limited erasing speed and bad tracks. A flash ROM has a lifetime of about 100,000 erasures.
The drawback of saving CRC codes in a flash ROM or an EEPROM is that the CRC code has to be erased and rewritten every time any data is updated, even when only one byte is updated. Conventional methods typically handle this problem in one of two ways. The first way is to increase the physical capability of the flash ROM or EEPROM, such as improving erasure lifetime and erasing speed. The second way is to maintain a plurality of CRC codes for related data. In this way, the occasions of erasing one CRC code are distributed to a plurality of CRC codes.
With the increasing popularity of network and portable devices, the demand for storage capacity has been increasing commensurately. For example, downloading of data such as software and music requires updating of data stored in a storage system. These days, erasing of CRC codes is more frequent than ever.
In a flash ROM, a bit can be rewritten from the value 1 to the value 0, and can be erased from the value 0 to the value 1. Rewriting means changing a bit from a high level voltage that represents 1 to a low level voltage that represents 0. Erasing refers to changing a bit to a high level voltage that can be rewritten. One byte comprises 8 bits, and may for example have a binary numerical value 11110101. This byte can be rewritten as 101000101, since any corresponding bit having a value 1 can be rewritten to the value 0. Said byte cannot for example be rewritten as 10011101, since the fifth bit of the byte has a value 0 that cannot be rewritten as the value 1. So it is necessary to erase the byte to 11111111, and then rewrite it to 10011101. Conventional methods have not adequately taken advantage of this characteristic of flash ROMs. Thus, there exists a need for a method and apparatus that can reduce the number of erasures of CRC codes in a flash ROM.